#pragma once
#include <iostream>
#include <vector>
#include <list>

#define MAX_in 0

int max( int i, int j )
{
  if ( i >= j )
    return i;
  else
    return j;
};

/// Graph class
///
/// CONSTRUCTION: zero parameter
///
/// ******************PUBLIC OPERATIONS*********************
/// void Setmode( x )                  --> set mode as x
/// void import( vec )                 --> import vec
/// void Add_Edge( u, v, element )     --> add Edge between ( u, v ) with element as weight
/// void Reset_Edge( u, v, element )   --> reset Edge between ( u, v ) with element as weight
/// void Remove_Vertex( u )            --> Remove Vertex u
/// void Remove_Edge( u, v )           --> Remove Edge between ( u, v )
/// void listVertexes()                --> list all Vertexes
/// void listEdges()                   --> list all Edges in the specified form out of order
/// ******************ERRORS********************************
/// Throws UnderflowException as warranted

template <typename DT>
class Graph
{
 private:
  
  /**
   *V_num表示整张图中所含顶点的个数，即为序列Vec中非零元素的个数;
   *V_max为整张图中曾出现或者即将插入的顶点中的最大值加一，
   *即为序列Vec的大小，且V_max还用以扩充邻接矩阵或者邻接表的大小，避免插入时越界。
   *
   *E_num表示整张图中所含边的数量，在边的插入、删除，及点的删除过程中并行计算。
   *
   *Vec中存储了所有点的入度和出度和，如果为0则该点不存在。
   *
   *Sto_{mode}$表示该图的存储方式，初始值为0,若指定为1则采用邻接表存储无权图，
   *若指定为2则采用邻接矩阵存储有权图。若用户没有指定存储方式，
   *则根据第一次加入的边来确定：如果第一次加入一无权边或者权重为1的边则指定为1,否则指定为2。
   */
  int V_num;
  int V_max;
  int E_num;
  std::vector<int> Vec;                               //store the sum of the in and out degrees for each Vertex

  /**
   *the node of the adjacency list (set to an unauthorized graph)
   *add element to the structure serves as the node of the authority graph
   */
  struct ad_list 
  {
    int vertex;
    struct ad_list* next = nullptr;
  };
  typedef ad_list* AD_list;

  std::vector<AD_list> ad_lists;                      //adjacency list
  std::vector<std::vector<DT>> adj_lists;               //adjacency matrix
  int Sto_mode = 0;                                   //storage mode. 1, using the adjacency list; 2, using the adjacency matrix 

  /**
   *determine whether the Vertex has been added to the graph
   */
  bool validateVertex( int v )
  {
    if ( v < 0 || v >= V_max || Vec[v] == 0 )
      {
	return false;
      }
    return true;
  }

  /**
   *make the distance from each Vertex to itself always zero
   */
  void balance()
  {
    for ( int i = 0; i < V_max; i++ )
      adj_lists[i][i] = 0;
  }

  /**
   *add the Edge to the adjacency list
   */
  void add_Edge( int u, int v )
  {
    bool contained = false;
    if ( max( u, v ) >= ad_lists.size() )                        //if the Vertex value is larger than the 
      {                                                          //vector's size, enlarge the vector's size
	for ( int i = V_max; i <= max( u, v ); i++ )
	  {
	    ad_lists.push_back( new( struct ad_list ) );
	    ad_lists[i]->vertex = i;
	    ad_lists[i]->next = nullptr;
	  }
	V_max = max( u, v ) + 1;
	Vec.resize( V_max, 0 );
      }
    AD_list list;
    list = new( struct ad_list );
    list->vertex = v;
    AD_list list0 = ad_lists[u];
    for ( list0; list0->next != nullptr; list0 = list0->next )
      if ( list0->next->vertex == v ) { contained = true; break; }     //if the Edge already exists in the graph,
    if ( !contained )                                            //this operation is ignored
      { list0->next = list; E_num++; Vec[u]++; Vec[v]++; }
    else
      std::cout << "This edge between ( " << u << ", " << v << " ) has been set." << std::endl;
  }

  /**
   *add the Edge to the adjacency matrix 
   *with element as its weight
   */
  void add_Edge( int u, int v, DT element )
  {
    if ( element != 0 )
      {
	if ( max( u, v ) >= V_max )
	  {
	    adj_lists.resize( max( u, v ) + 1, std::vector<DT>( max( u, v ) + 1, MAX_in ) ); //if the Vertex value is larger than the 
	    for ( int i = 0; i < V_max; i++ )                                                //vector's size, enlarge the vector's size
	      adj_lists[i].resize( max( u, v ) + 1, MAX_in );
	    V_max = max( u, v ) + 1;
	    Vec.resize( V_max, 0 );
	  }
	if ( adj_lists[u][v] == MAX_in && u != v )                                           //if the Edge already exists in the graph, 
	  {                                                                                  //this operation is ignored
	    adj_lists[u][v] = element;
	    E_num++;
	    balance(); Vec[u]++; Vec[v]++;
	  }
	else if ( adj_lists[u][v] != MAX_in )
	  std::cout << "This edge between ( " << u << ", " << v << " ) has been set." << std::endl;
      }
  }
  
  /**
   *delete all Edges participating in and 
   *Vertex u within the specified range ( m, n )
   */
  void remove( int m, int n, int u )
  {
    for ( int i = m; i < n; i++ )
      {
	for ( AD_list Node = ad_lists[i]; Node->next != nullptr; Node = Node->next )
	  {
	    if ( Node->next->vertex == u )
	      {
		AD_list node = Node->next;
		Node->next = node->next;
		delete( node );
		E_num--;
		break;
	      }
	    if ( Node->next->next == nullptr && Node->next->vertex == u )
	      { delete( Node->next ); Node->next = nullptr; E_num--; break; }
	  }
      }
  }

  /**
   *use iteration to delete all 
   *nodes after the node list
   */
  void deleteNode( AD_list list )
  {
    if ( list == nullptr );
    else if ( list->next != nullptr )
      deleteNode( list->next ); 
    else
      { delete( list ); E_num--; }
  }

  /**
   *clear the graph
   */
  void makeEmpty()
  {
    if ( Sto_mode == 1 )
      {
	for ( int i = 0; i < V_max; i++ )
	  deleteNode( ad_lists[i] );
	ad_lists.clear();
      }
    else if ( Sto_mode == 2 )
      {
	adj_lists.clear();
      }
    Sto_mode = 0;
  }
  
 public:
  Graph()
    {
      V_num = 0;
      V_max = 0;
      E_num = 0;
    }

  /**
   *copy graph
   */
  Graph( const Graph & gra )
    {
      Sto_mode = gra.Sto_mode;
      if ( Sto_mode == 1 )
	{
	  for ( int i = 0; i < gra.V_max; i++ )
	    ad_lists.push_back( gra.ad_lists[i] );
	}
      else if ( Sto_mode == 2 )
	{
	  for ( int i = 0; i < gra.V_max; i++ )
	    adj_lists.push_back( gra.adj_lists[i] );
	}
      E_num = gra.E_num;
      V_num = gra.V_num;
      V_max = gra.V_max;
      for ( int i = 0; i < V_max; i++ )
	Vec.push_back(gra.Vec[i]);
    }

  /**
   *destructor for the graph
   */
  ~Graph()
    {
      makeEmpty();
    }

  /**
   *set the mode for the storage mode
   */
  void Setmode( const int & mode )
  {
    if ( Sto_mode == 1 || Sto_mode == 2 )
      std::cout << "The mode has been chosen." << std::endl;
      else
	{
	  if ( mode != 1 && mode != 2 )
	    std::cout << "Wrong mode!" << std::endl;
	  else
	    Sto_mode = mode;
	}
  }

  void Setmode( int && mode )
  {
    if ( Sto_mode == 1 || Sto_mode == 2 )
      std::cout << "The mode has been chosen." << std::endl;
    else
      {
	if ( std::move( mode ) != 1 && std::move( mode ) != 2 )
	  std::cout << "Wrong mode!" << std::endl;
	else
	  Sto_mode = mode;
      }
  }

  /**
   *import a two-dimensional array that 
   *is stored as an adjacency matrix by 
   *default without prior declaration
   */
  void import( const std::vector<std::vector<DT>> & vec )
  {
    if ( Sto_mode == 1 )
      {
	for ( int i = 0; i < vec.size(); i++ )
	  for ( int j = 0; j < vec[i].size(); j++ )
	    if ( vec[i][j] != 0 )
	      add_Edge( i, j );
      }
    else if ( Sto_mode == 0 || Sto_mode == 2 )
      {
	Sto_mode = 2;
	for ( int i = 0; i < vec.size(); i++ )
	  for ( int j = 0; j < vec[i].size(); j++ )
	    add_Edge( i, j, vec[i][j] );
	balance();
      }
  }

  /**
   *add the Edge to the adjacency matrix 
   *with element as its weight
   */
  void Add_Edge( int u, int v, DT element = 1 )
  {
    if ( element == 1 && Sto_mode == 0 )
      Sto_mode = 1;
    if ( Sto_mode == 1 && element != 0 )
      add_Edge( u, v );
    else
      add_Edge( u, v, element );
  }

  /**
   *reset the Edge to the adjacency matrix 
   *with element as its weight
   */
  void Reset_Edge( int u, int v, int element )
  {
    if ( element != MAX_in )
      {
	if ( adj_lists[u][v] == MAX_in )
	  std::cout << "This edge between ( " << u << ", " << v << " )  isn't set." << std::endl;
	else
	  adj_lists[u][v] == element;
      }
    else
      Remove_Edge( u, v );
  }

  /**
   *remove the Vertex u, and delete the all
   *Edges it participates in
   */
  void Remove_Vertex( int u )
  {
    if ( validateVertex( u ) )
      {
	if ( Sto_mode == 1 )
	  {
	    remove( 0, u, u );
	    deleteNode( ad_lists[u]->next );
	    ad_lists[u]->next = nullptr;
	    remove( u + 1, V_max, u );
	  }
	else if ( Sto_mode == 2 )
	  {
	    for ( int i = 0; i < V_max; i++ )
	      if ( adj_lists[u][i] != MAX_in )
		{ adj_lists[u][i] = MAX_in; E_num--; }
	    for ( int i = 0; i < V_max; i++ )
	      if ( adj_lists[i][u] != MAX_in )
		{ adj_lists[i][u] = MAX_in; E_num--; }
	  }
	Vec[u] = 0;
      }
    else
      std::cout << "vertex " << u << " is invalid." << std::endl;
  }

  /**
   *remove the Edge between ( u, v )
   */
  void Remove_Edge( int u, int v )
  {
    if ( validateVertex( u ) && validateVertex( v ) )
      {
	if ( Sto_mode == 1 )
	  {
	    remove( u, u + 1, v );
	    if ( ad_lists[u]->next == nullptr )
	      Vec[u]--;
	    if ( ad_lists[v]->next == nullptr )
	      Vec[v]--;
	  }
	else if ( Sto_mode == 2 )
	  {
	    bool check = true;
	    if ( adj_lists[u][v] != MAX_in )
	      {
		adj_lists[u][v] = MAX_in;
		for ( int i = 0; i < V_max; i++ )
		  if ( adj_lists[u][i] == MAX_in )
		    { check = false; break; }
		if ( check ) Vec[u]--;
		check = true;
		for ( int i = 0; i < V_max; i++ )
		  if ( adj_lists[v][i] == MAX_in )
		    { check = false; break; }
		if ( check ) Vec[v]--;
		E_num--;
	      }
	  }
      }
    if ( !validateVertex( u ) )
      std::cout << "vertex " << u << " is invalid." << std::endl;
    if ( !validateVertex( v ) )
      std::cout << "vertex " << v << " is invalid." << std::endl;
  }

  /**
   *list all Vertexes
   */
  void listVertexes()
  {
    if ( Sto_mode == 0 )
      std::cout << "With no vertex." << std::endl;
    else
      {
	V_num = 0;
	for ( int i = 0; i < V_max; i++ )
	  if ( Vec[i] != 0 ) { std::cout << i << " " ; V_num++; }
	std::cout << std::endl;
      }
    std::cout << "The Graph contains " << V_num << " vertexes." << std::endl;
  }

  /**
   *list all Edges in the specified form out of order
   */
  void listEdges()
  {
    if ( Sto_mode == 0 )
      std::cout << "With no edge." << std::endl;
    else if ( Sto_mode == 1 )
      {
	for ( int i = 0; i < V_max; i++ )
	  for ( struct ad_list* list = ad_lists[i]->next; list != nullptr; list = list->next )
	    std::cout << "(" << i << ", " << list->vertex << ", 1)" << std::endl;
      }
    else if ( Sto_mode == 2 )
      {
	for ( int i = 0; i < V_max; i++ )
	  for ( int j = 0; j < V_max; j++ )
	    if( adj_lists[i][j] != MAX_in )
	      std::cout << "(" << i << ", " << j << ", " << adj_lists[i][j] << ")" << std::endl; 
      }
  std::cout << "The Graph contains " << E_num << " edges." << std::endl;
  }
  
};
